package com.shuang.greed8;

public class CanCompleteCircuit {
    //贪心：
    //rest[i] = gas[i]-cost[i] 为一天剩下的油
    //局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。
    //全局最优：找到可以跑一圈的起始位置。
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //用于计算当前剩下的油量和
        int curSum = 0;
        //最后剩余的油量总和
        int totalSum = 0;

        //最后选择的出发时的索引位置
        int index = 0;

        for (int i = 0; i < gas.length; i++){
            //计算走到当前位置的油量和
            curSum += gas[i] - cost[i];

            if (curSum < 0){
                //走到当前位置油量和是小于零的 至少要从当前的下一个位置开始走
                index = i + 1;
                //遍历下个位置时 重新开始计算后续的油量和
                curSum = 0;
            }

            //计算剩余油量总和
            totalSum += gas[i] - cost[i];
        }

        //最后判断油量总和
        if (totalSum < 0){
            //最后油量总和小于零 说明加的油量肯定不够循环一周消耗的 没有解
            return -1;
        }

        return index;
    }
}
